import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class StackOfPlates {
    private List<Deque<Integer>> list = new ArrayList<>();
    private int capacity = 0;
    private int cur_index = 0; // 记录最后一个栈所在的位置!
    public StackOfPlates(int cap) {
        this.capacity = cap;
    }

    public void push(int val) {
        if(list.size() == 0){
            list.add(new LinkedList<>());
        }
        if(list.get(cur_index).size() == capacity){
            list.add(new LinkedList<>());
            cur_index++;
        }
        list.get(cur_index).push(val);
    }

    public int pop() {
        // 逻辑上讲应该把最后一个栈的栈顶元素pop 但是
        // 最后一个栈可能被抛空
        // 那就要向前找到上一个还没有被pop空的栈!
        if(cur_index < 0) return -1;

        while(cur_index >= 0 && list.get(cur_index).isEmpty()){
            list.remove(cur_index);
            cur_index--;
        }

        if(cur_index < 0) return -1;

        int val = list.get(cur_index).pop();

        // 可能pop完最后一个就空了!
        if(list.get(cur_index).isEmpty()){
            list.remove(cur_index);
            cur_index--;
        }

        return val;
    }

    public int popAt(int index) {
        if(index > cur_index) return -1;

        int val = list.get(index).pop();

        if(list.get(index).isEmpty()){
            list.remove(index);
            cur_index--;
        }
        return val;
    }

    public static void main(String[] args) {
        StackOfPlates stackOfPlates = new StackOfPlates(2);

        stackOfPlates.push(1);
        stackOfPlates.push(2);
        stackOfPlates.push(3);
        stackOfPlates.popAt(0);
        stackOfPlates.popAt(0);
        stackOfPlates.popAt(0);

    }
}
